Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського»  ЗВІТ до лабораторної роботи № 3 з дисципліни «Програмування складних алгоритмів» Тема «Методи сортування» Варіант № 11                             Лабораторна робота № 3: Методи сортування Мета: набуття практичних навичок з використання простих методів сортування. 1.1. Завдання до роботи Провести сортування масивів вказаним методом та у вказаному порядку. Для тестування алгоритмів сортування масив (10x10, та більше бажанням). Самостійно обрати додатковий метод та провести сортування того ж масиву. Порівняти кількість перестановок (або час виконання) обох методів. Спробувати порівняти час виконання сортування з масивом більшого розміру, який створити за допомогою генератора випадкових чисел. Завдання відповідно варіанту: Метод сортування: сортування методом вставки. / 1.2. Теоретичні відомості Сортування даних – невід’ємна частина аналізу даних. Воно дає можливість відсортувати список імен в алфавітному порядку, скласти список продуктів за рівнем запасів (від найбільшого до найменшого) або впорядкувати рядки за кольорами чи піктограмами. Алгоритм сортування - це алгоритм, який сортує масиви даних. Різні типи алгоритмів сортування включають: сортування вибором (Selection Sort); сортування вставкою (Insertion Sort); сортування обміном (Bubble Sort); швидке сортування (Quick Sort); сортування підрахунком (Counting Sort) тощо. Сортування вибором (Selection Sort) — простий алгоритм сортування лінійного масиву, на основі вставок. Має ефективність n2, що робить його неефективним при сортування великих масивів, і в цілому, менш ефективним за подібний алгоритм сортування включенням. Сортування вибором вирізняється більшою простотою, ніж сортування включенням, і в деяких випадках, вищою продуктивністю. Для сортування масиву методом вибору від найменшого до найбільшого елементу виконуються наступні кроки: Починаючи з елементу під індексом 0, шукаємо в масиві найменше значення. Знайдене значення міняємо місцями з нульовим елементом. Повторюємо кроки №1 і №2 уже для наступного індексу в масиві (відсортований елемент більше не чіпаємо). Іншими словами, ми шукаємо найменший елемент в масиві і переміщуємо його на перше місце. Потім шукаємо другий найменший елемент і переміщуємо його вже на друге місце після першого найменшого елемента. Цей процес триває до тих пір, поки в масиві не закінчаться невідсортовані елементи. Приклад коду: for(int i = 0; i < N-1; i++) { int min_indx = i; for(int j = i; j < N; j++) { if (mas[j] < mas[min_indx]) { min_indx = j; } } if (i != min_indx) { int tmp = mas[i]; mas[i] = mas[min_indx]; mas[min_indx] = tmp; } } Сортування вставками (Insertion sort) - алгоритм сортування, в якому елементи вхідної послідовності проглядаються по одному, і кожен новий елемент, що надійшов, розміщується в відповідне місце серед раніше впорядкованих елементів. Обчислювальна складність – О(n2). Приклад коду: void Sort(int* arr, int n){ int counter = 0; for(int i = 1; i < n; i++){ for(int j = i; j > 0 && arr[j-1] > arr[j]; j--){ counter++; int tmp = arr[j-1]; arr[j-1] = arr[j]; arr[j] = tmp; } } Cout << counter << endl; } Сортування обміном (також відоме як сортування методом бульбашки) полягає в тому, що всі сусідні елементі вихідного масиву попарно порівнюються один з одним і міняються місцями, якщо попередній елемент більший, або менший в залежності від типу сортування (за зростанням чи за спаданням) від наступного. В результаті максимальний (мінімальний) елемент поступово зміщується вправо і після першого такого перегляду займе крайнє праве положення. Потім процес перегляду повторюється, і своє місце займає другий за величиною елемент, який також виключається з подальшого розгляду. Продовжуючи даний процес далі, на останньому кроці отримаємо впорядковану послідовність. Обчислювальна складність – ...